import java.util.Arrays;


public class Leetcode34 {
    public static void main(String[] args) {
        System.out.println(Arrays.toString(searchRange(new int[]{2, 2, 3}, 2)));
    }

    public static int[] searchRange(int[] nums, int target) {
        if (nums.length == 0) {
            return new int[]{-1, -1};
        }
        int[] res = new int[2];
        int left = 0;
        int right = nums.length - 1;

        while (left < right) {
            int middle = (right - left) / 2 + left;
            if (nums[middle] >= target) {
                right = middle;
            } else {
                left = middle + 1;
            }
        }

        if (nums[left] != target) {
            return new int[]{-1, -1};
        }

        res[0] = left;

        right = nums.length;
        while (left < right) {
            int middle = (right - left) / 2 + left;
            if (nums[middle] > target) {
                right = middle;
            } else {
                left = middle + 1;
            }
        }

        res[1] = left - 1;

        return res;
    }

}

